package com.algorithm.sort;

import java.util.Arrays;

/**
 * @program: study
 * @className: CountSort
 * @description: 计数排序
 * @author: kukuxiahuni
 * @create: 2020-01-07 10:32
 * @version: v1.0
 **/
public class CountSort {

    public static void main(String[] args) {
        int[] array = {2, 5, 3, 0, 2, 3, 0, 3};
        countSort(array);
    }


    /**
     * 功能描述: 计数排序
     * 1. 统计数据的范围：并创建计数数组，数组中的值为数组下标数值的计数
     * 2. 数据计数，将其结果存入到计数数组中；
     * 3. 计数数组数据累加；
     * 4. 创建与待排序数组相同的临时数组，进行排序数据
     * 5. 数据拷贝（可以不用这个）
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/7 10:33 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/7 10:33 上午
     **/
    private final static void countSort(int[] array) {

        if (array == null || array.length <= 1) {
            return;
        }
        //1. 最大值
        int max = Arrays.stream(array).max().getAsInt();

        //2. 计数数组
        int[] countArray = new int[max + 1];

        //3. 数据计数
        for (int n : array) {
            countArray[n]++;
        }

        //4. 计数数组数据按照索引累加
        for (int i = 1; i <= max; ++i) {
            countArray[i] = countArray[i - 1] + countArray[i];
        }

        //5. 数据排序:注意此处，容易出错
        int[] tmp = new int[array.length];
        for (int i = array.length - 1; i >= 0; --i) {
            int index = countArray[array[i]] - 1;
            tmp[index] = array[i];
            countArray[array[i]]--;
        }

        array = tmp;
        for (int n : array) {
            System.out.println(n);
        }


    }
}
